1. Field of the Invention
The present invention is generally related to multiprocessor networks. More particularly, the present invention is directed to adaptive packet routing among switches and endpoints in a cluster-type interconnection network.
2. Description of Related Art
Large scale computing systems such as cluster computers support a wide variety of applications and services. Such systems may include multiple devices distributed across an interconnection network/switch fabric. Each node of the network may include a switch (e.g., a router) or an endpoint (e.g., a host device). Typically, a routing algorithm is used to determine the path through the network between each pair of source and destination devices.
The routing algorithm may be implemented by programming a lookup table (“LUT”) in each switch (router) chip in the network. For instance, the LUT is indexed by the destination address and produces an output port based on the contents programmed in the LUT. By taking into account a congestive state of the network, the routing algorithm decides which path (output port) is the “best” choice based on a heuristic. The goal of the routing algorithm is to evenly use the available links, or “load balance” the network, by spreading the offered traffic across as many links possible while still providing deadlock-free operation.
The interconnection network may be arranged in different configurations (topologies). For instance, an array of devices may be configured in a mesh, torus, flattened butterfly or generalized hypercube architecture. In one architecture, switching chips are used to build fat-trees of folded-Clos networks. In this architecture, a packet can take one of several paths as it traverses from the source (injection) host to the common ancestor at the root of the tree. Here, adaptive routing helps to load balance the available paths in the network by evenly distributing the offered load across the available physical channels. Alternative topologies, such as the flattened butterfly and generalized hypercube, are direct networks that require adaptive routing to load balance the links and provide good latency-bandwidth characteristics for arbitrary traffic.